/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/insert-into-a-cyclic-sorted-list
   @Language: C++
   @Datetime: 19-03-14 15:44
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */


class Solution {
public:
	/*
	 * @param node: a list node in the list
	 * @param x: An integer
	 * @return: the inserted new list node
	 */
	ListNode * insert(ListNode * node, int x) {
		if (node==NULL){
			node = new ListNode(x,NULL);
			node->next = node;
			return node;
		}
		// find biggest node
		for(ListNode *visit=node; node->val<=node->next->val && visit!=node->next; node=node->next);
		if (node->val<=x){
			node->next = new ListNode(x,node->next);
			return node->next;
		}
		for(; node->next->val<x; node=node->next);
		node->next = new ListNode(x,node->next);
		return node->next->next;
	}
};
